package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*

/*
    https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
    https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_104-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%A4%A7%E6%B7%B1%E5%BA%A6

    104. 二叉树的最大深度
    给定一个二叉树 root ，返回其最大深度。
    二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：
输入：root = [1,null,2]
输出：2
 */
class leetcode_104 {
    @Test
    fun test_1() {
        val n3 = TreeNode(3)
        val n9 = TreeNode(9)
        val n20 = TreeNode(20)
        val n15 = TreeNode(15)
        val n7 = TreeNode(7)
        n3.left = n9
        n3.right = n20
        n20.left = n15
        n20.right = n7

        val actual = maxDepth(n3)
        val expected = 3
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val root = TreeNode(1)
        val n2 = TreeNode(2)
        root.right = n2

        val actual = maxDepth(root)
        val expected = 2
        Assert.assertEquals(expected, actual)
    }

    private fun maxDepth(root: TreeNode?): Int {
//        return maxDepth1(root)
        return maxDepth2(root)
//        return maxDepth3(root)
    }

    // 方法1:
    private fun maxDepth1(root: TreeNode?): Int {
        // 广度遍历- 求深度
        // S - N
        // T - N
        if (null == root) return 0
        var depth: Int = 0
        val queue: LinkedList<TreeNode> = LinkedList<TreeNode>()
        queue.offer(root)
        while (!queue.isEmpty()) {
            depth++
            var size = queue.size
            while (size-- > 0) {
                val node: TreeNode = queue.poll()
                node.left?.let { queue.offer(it) }
                node.right?.let { queue.offer(it) }
            }
        }
        return depth
    }

    // 方法2:
    var maxDepth: Int = 0
    private fun maxDepth2(root: TreeNode?): Int {
        // 深度遍历 - 前置遍历 - 求深度,深度回溯
        if (null == root) {
            return 0
        }
        getDepth(root, 1)
        return maxDepth
    }

    private fun getDepth(root: TreeNode?, currentDeepth: Int) {
        if (null == root) {
            return
        }
        // 中
        if (root.left == null && root.right == null && currentDeepth > maxDepth) {
            maxDepth = currentDeepth
            return
        }
//        var height: Int = currentDeepth
//        if (root.left != null) { // 左
//            height++
//            getDepth(root.left, height)
//            height--
//        }
//        if (root.right != null) { // 右
//            height++
//            getDepth(root.right, height)
//            height--
//        }
        if (root.left != null) { // 左
            getDepth(root.left, currentDeepth+1)
        }
        if (root.right != null) { // 右
            getDepth(root.right, currentDeepth+1)
        }
    }

    // 方法三
    private fun maxDepth3(root: TreeNode?): Int {
        // 深度遍历 - 后置遍历 - 求高度。最大深度和最大高度是一样的
        return getHeight(root)
    }

    private fun getHeight(root: TreeNode?): Int {
        // T - N
        // S - N
        if (null == root) {
            return 0
        }
        // 左
        val leftHeight: Int = getHeight(root.left)
        // 右
        val rightHeight: Int = getHeight(root.right)
        // 中
        val maxChildHeight = Math.max(leftHeight, rightHeight)
        val maxHeight: Int = 1 + maxChildHeight
        return maxHeight
    }
}